package com.dmall.graph.floodfill;

public class Leetcode785 {

    private boolean[] visited;
    private int[] colors;
    private int[][] graph;

    public boolean isBipartite(int[][] graph) {

        this.graph = graph;
        if (graph[0].length == 0) {
            return false;
        }

        int R = graph.length;
        visited = new boolean[R];
        colors = new int[R];

        for (int i = 0; i < R; i++) {
            if (!visited[i]) {
                if (!dfs(i, 0)) {
                    return false;
                }
            }
        }

        return true;
    }

    private boolean dfs(int v, int color) {
        visited[v] = true;
        colors[v] = color;
        for (int w : graph[v]) {
            if (!visited[w]) {
                if (!dfs(w, 1 - color)) {
                    return false;
                }
            } else if (colors[v] == colors[w]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        //int[][] graph = {{1,3}, {0,2}, {1,3}, {0,2}};
        int[][] graph = {{1,2,3}, {0,2}, {0,1,3}, {0,2}};
        Leetcode785 leetcode785 = new Leetcode785();
        boolean bipartite = leetcode785.isBipartite(graph);
        System.out.println(bipartite);
    }
}
